package com.example.queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 仅使用两个栈实现先入先出队列。
 * 队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
 */
public class Leetcode232_MyQueueByTwoStacks {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        System.out.println(queue.pop());
        System.out.println(queue.peek());
        System.out.println(queue.pop());
        System.out.println(queue.peek());
        System.out.println(queue.pop());
    }

    /**
     * 两个栈:
     * push时直接往一个栈中(stack1)push即可
     * <p>
     * pop/peek时先检查另外一个(stack2)是否为空
     * 不为空，直接返回栈顶元素
     * 为空:先将stack1的所有元素pop出来，并push到stack中，最后返回stack2中栈顶元素
     */
    private static class MyQueue {
        private Deque<Integer> stack1 = new LinkedList();
        private Deque<Integer> stack2 = new LinkedList<>();

        public MyQueue() {

        }

        public void push(int x) {
            stack1.push(x);
        }


        public int pop() {
            if (size()== 0) {
                return -1;
            }
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }

        public int peek() {
            if (size()== 0) {
                return -1;
            }
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }

        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }

        public int size() {
            return stack1.size() + stack2.size();
        }
    }
}
